
import numpy 
from PIL import Image
import matplotlib.pyplot as plt
def pretreatment(str):
    ima=Image.open(str) #读入图像
    w, h = ima.size
    ima=ima.convert('L') 
    im=numpy.array(ima)        #转化为二维数组
    for i in range(im.shape[0]):#转化为二值矩阵
        for j in range(im.shape[1]):
            if im[i,j]==255:
                im[i,j]='0'
            else:
                im[i,j]='1'
    return (im,w,h)

def Array2D(w, h,data):
    def showArray2D():
        numpy.savetxt("a.txt", data, fmt = '%d', delimiter = ',')
    return {
        'w': w,
        'h': h,
        'data': data,
        'showArray2D': showArray2D
    }

def Point(x, y):
    return {
        'x': x,
        'y': y,
        'eq': lambda other: other['x'] == x and other['y'] == y
    }

def AStart(mapData, startPoiot, endPoint, passTag):
    openList = []
    closeList = []
    currentNode = None
    minF = None
    
    def generateNode(point):
        return {
            'point': point,
            'parent': None,
            'g': 0,
            'h': (abs(endPoint['x'] - point['x']) + abs(endPoint['y'] - point['y'])) * 10
        }
    
    def pointInCloseList(point):
        for node in closeList:
            if node['point']['eq'](point):
                return node
        return None
    
    def pointInOpenList(point):
        for node in openList:
            if node['point']['eq'](point):
                return node
        return None
    
    def endPointInCloseList():
        for node in closeList:
            if node['point']['eq'](endPoint):
                return node
        return None
    
    def findFMinPoint():
        node = openList[0]
        for point in openList[1:]:
            if point['h'] + point['g'] < node['h'] + node['g']:
                node = point
        return node
    
    def search(minNode, offsetX, offsetY):
        x = minNode['point']['x'] + offsetX
        y = minNode['point']['y'] + offsetY
        step = 10 if offsetX == 0 or offsetY == 0 else 14
        
        if x < 0 or y < 0 or x > mapData['h'] - 1 or y > mapData['w'] - 1:
            return None
        
        if mapData['data'][x][y] != passTag:
            return None
        
        currentPoint = Point(x, y)
        if pointInCloseList(currentPoint):
            return None
        currentNode = pointInOpenList(currentPoint)
        if currentNode is None:
            currentNode = generateNode(currentPoint)
            currentNode['g'] = minNode['g'] + step
            currentNode['parent'] = minNode
            openList.append(currentNode)
            return None
        if minNode['g'] + step < currentNode['g']:
            currentNode['g'] = minNode['g'] + step
            currentNode['father'] = minNode
    
    def start():
        currentNode = generateNode(startPoiot)
        openList.append(currentNode)
        res = []
        x = endPoint['x'] 
        y = endPoint['y'] 
        if mapData['data'][x][y] !=passTag:
            return -1
        while True:
            minF = findFMinPoint()
            index = openList.index(minF)
            openList.pop(index)
            closeList.append(minF)
            
            search(minF, 0, 1)
            search(minF, 1, 0)
            search(minF, 0, -1)
            search(minF, -1, 0)
            search(minF, 1, 1)
            search(minF, -1, 1)
            search(minF, -1, -1)
            search(minF, 1, -1)
            
            point = endPointInCloseList()
            if point:
                cpoint = point
                while True:
                    if cpoint['parent']:
                        res.append((cpoint['point']['y'],cpoint['point']['x']))
                        cpoint = cpoint['parent']
                    else:
                        return res[::-1]
            
            if len(openList) == 0:
                return None

    return start()


# im,w,h=pretreatment('./hbl/hbl_6.bmp')  #调用图像预处理函数

# mapData = Array2D(w, h, im)
# ima=Image.open('./hbl/hbl_6.bmp') #读入图像

# res = AStart(mapData, Point(65, 105), Point(41,60), 0)
# print(res)
# for i in res:
#   mapData['data'][i[1]][i[0]]='2'
# mapData['showArray2D']()
# numpy.savetxt("a.txt", im, fmt = '%d', delimiter = ',')
# matrix = numpy.array(ima)
# plt.imshow(matrix, cmap='gray', interpolation='nearest')
# plt.axis('off')  # 去除坐标轴
# plt.show()